/**
 * 25. K 个一组翻转链表
 * https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 * 进阶：
 */
public class Solutions_25 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode cur = head;
        cur.next = new ListNode(2);
        cur = cur.next;
        cur.next = new ListNode(3);
        cur = cur.next;
        cur.next = new ListNode(4);
        cur = cur.next;
        cur.next = new ListNode(5);

//        int k = 2;  // output: {2, 1, 4, 3, 5}
//        int k = 3;  // output: {3, 2, 1, 4, 5}
//        int k = 4;  // output: {4, 3, 2, 1, 5}
        int k = 5;  // output: {5, 4, 3, 2, 1}
//        int k = 1;  // output: {1, 2, 3, 4, 5}

        ListNode result = reverseKGroup(head, k);
        System.out.println(result);
    }

    // 模拟实现
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode res = new ListNode(-1);
        ListNode dummy = res;

        int len = 0;
        ListNode cur = head;
        // 1.统计出链表长度
        while (cur != null) {
            len ++;
            cur = cur.next;
        }
        if (k <= 1 || len < k) {
            // 翻转不了，直接返回结果
            return head;
        }
        cur = head;
        while (len >= k) {
            // 能够翻转的情况，每 k 个进行翻转
            ListNode hair = null, newHead = cur;
            int count = k;
            while (count > 0) {
                // 翻转
                ListNode tempNext = cur.next;
                cur.next = hair;
                hair = cur;
                cur = tempNext;
                count --;
            }
            len -= k;
            // 结果链表的下一节点指向 pre，即翻转过的 k 个结点
            dummy.next = hair;
            // dummy 指向翻转前的头结点，翻转后则成为了尾结点
            dummy = newHead;
        }
        // 拼接上剩余的节点，或置空
        dummy.next = cur;
        return res.next;
    }
}
